//
//  Problem872.swift
//  TestProject
//
//  Created by 武侠 on 2021/6/4.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 872. 叶子相似的树
 请考虑一棵二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。

 举个例子，如上图所示，给定一棵叶值序列为 (6, 7, 4, 9, 8) 的树。
 如果有两棵二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的。
 如果给定的两个根结点分别为 root1 和 root2 的树是叶相似的，则返回 true；否则返回 false 。
 
 示例 1：
     输入：root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
     输出：true
 示例 2：
     输入：root1 = [1], root2 = [1]
     输出：true
 示例 3：
     输入：root1 = [1], root2 = [2]
     输出：false
 示例 4：
     输入：root1 = [1,2], root2 = [2,2]
     输出：true
 示例 5：
     输入：root1 = [1,2,3], root2 = [1,3,2]
     输出：false
 提示：
     给定的两棵树可能会有 1 到 200 个结点。
     给定的两棵树上的值介于 0 到 200 之间。
 */
@objcMembers class Problem872: NSObject {
    func solution() {
        let root1 = TreeNode(3)
        root1.left = TreeNode(5)
        root1.left?.left = TreeNode(6)
        root1.left?.right = TreeNode(2)
        root1.left?.right?.left = TreeNode(7)
        root1.left?.right?.right = TreeNode(4)
        
        root1.right = TreeNode(1)
        root1.right?.left = TreeNode(9)
        root1.right?.right = TreeNode(8)
        
        let root2 = TreeNode(3)
        root2.left = TreeNode(5)
        root2.left?.left = TreeNode(6)
        root2.left?.right = TreeNode(7)
        
        root2.right = TreeNode(1)
        root2.right?.left = TreeNode(4)
        root2.right?.right = TreeNode(2)
        root2.right?.right?.left = TreeNode(9)
        root2.right?.right?.right = TreeNode(8)
        
        print(leafSimilar(root1, root2))
    }
    
    /*
     思路：
     1: 求出每棵树的叶序列，
     2: 对比2个序列是否相等
     
     */
    func leafSimilar(_ root1: TreeNode?, _ root2: TreeNode?) -> Bool {
        let list1 = getTreeLeafListBFS(root1)
        let list2 = getTreeLeafListBFS(root2)
        print(list1)
        print(list2)
        if list1.count != list2.count {
            return false
        }
        for i in 0..<list1.count {
            if list1[i] != list2[i] {
                return false
            }
        }
        
        return true
    }
    
    /*
     DFS：深度优先搜索 递归
     如果节点node没有左右子节点, 那么他就是叶节点，返回node的值
     如果有左右节点，那么返回左子树的叶列表 + 右子树的叶列表
     */
    func getTreeLeafList(_ root: TreeNode?) -> [Int] {
        if root == nil {
            return []
        } else if root?.left == nil, root?.right == nil {
            return [root!.val]
        }
        
        return getTreeLeafList(root?.left) + getTreeLeafList(root?.right)
    }
    
    /*
     BFS: 广度优先搜索
     1: 将root放入数组list中，
     2: 只要list中不为空，那么从0的位置取出一个节点，如果该节点为叶节点，放入结果集中
     3: 该节点有叶节点，那么把左右子节点放入数组list的头部，继续执行步骤2的判断
     */
    func getTreeLeafListBFS(_ root: TreeNode?) -> [Int] {
        if root == nil {
            return []
        } else if root?.left == nil, root?.right == nil {
            return [root!.val]
        }
        
        var node: TreeNode? = nil
        var result:[Int] = []
        var list:[TreeNode?] = [root]
        while list.isEmpty == false {
            node = list.removeFirst()
            if node == nil {
                continue
            }
            if node?.left == nil, node?.right == nil {
                result.append(node!.val)
            } else {
                list.insert(node?.right, at: 0)
                list.insert(node?.left, at: 0)
            }
        }
        
        return result
    }
}
